#define _CRT_SECURE_NO_WARNINGS 1
typedef struct ListNode LN;
void PushBack(LN** tail, LN* node) {
    (*tail)->next = node;
    *tail = node;
}
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL)
        return NULL;
    LN* cur = head;
    LN* smallhead, * smalltail;
    LN* gratehead, * gratetail;
    smallhead = smalltail = (LN*)malloc(sizeof(LN));
    gratehead = gratetail = (LN*)malloc(sizeof(LN));
    smallhead->next = smalltail->next = NULL;
    gratehead->next = gratetail->next = NULL;

    while (cur) {
        if (cur->val < x) {
            PushBack(&smalltail, cur);
        }
        else {
            PushBack(&gratetail, cur);
        }
        cur = cur->next;
    }
    if (smallhead->next == NULL) {
        return gratehead->next;
    }
    else if (gratehead->next == NULL) {
        return smallhead->next;
    }
    else {
        smalltail->next = gratehead->next;
        gratetail->next = NULL;
        return smallhead->next;
    }
}
